{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EN3BM2a0JLJR"
      },
      "source": [
        "##### Copyright 2020 Google"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "sVv2bPc0JMdM"
      },
      "outputs": [],
      "source": [
        "#@title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
        "# you may not use this file except in compliance with the License.\n",
        "# You may obtain a copy of the License at\n",
        "#\n",
        "# https://www.apache.org/licenses/LICENSE-2.0\n",
        "#\n",
        "# Unless required by applicable law or agreed to in writing, software\n",
        "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
        "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
        "# See the License for the specific language governing permissions and\n",
        "# limitations under the License."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yaieLbziJTX5"
      },
      "source": [
        "# Hardware grid circuits"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P2-jS0d9KI4r"
      },
      "source": [
        "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://www.example.org/cirq/experiments/qaoa/hardware_grid_circuits\"><img src=\"https://www.tensorflow.org/images/tf_logo_32px.png\" />View on QuantumLib</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/ReCirq/blob/master/docs/qaoa/hardware_grid_circuits.ipynb\"><img src=\"https://www.tensorflow.org/images/colab_logo_32px.png\" />Run in Google Colab</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://github.com/quantumlib/ReCirq/blob/master/docs/qaoa/hardware_grid_circuits.ipynb\"><img src=\"https://www.tensorflow.org/images/GitHub-Mark-32px.png\" />View source on GitHub</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a href=\"https://storage.googleapis.com/tensorflow_docs/ReCirq/docs/qaoa/hardware_grid_circuits.ipynb\"><img src=\"https://www.tensorflow.org/images/download_logo_32px.png\" />Download notebook</a>\n",
        "  </td>\n",
        "</table>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p7FRu0xXIfBW"
      },
      "source": [
        "The \"hardware grid\" problem is defined by a Hamiltonian whose topology matches the hardware graph natively. This permits a simple compilation (\"routing\") with circuit depth per p-step going like $O(1)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JgZdtr7hKaFJ"
      },
      "source": [
        "## Setup\n",
        "\n",
        "Install the ReCirq package:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "NN9a0rDMKa5G"
      },
      "outputs": [],
      "source": [
        "try:\n",
        "    import recirq\n",
        "except ImportError:\n",
        "    !pip install git+https://github.com/quantumlib/ReCirq"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H9heQyxwKkGG"
      },
      "source": [
        "Now import Cirq, ReCirq and the module dependencies:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "kVH-4o_bKoH_"
      },
      "outputs": [],
      "source": [
        "import cirq\n",
        "import recirq\n",
        "\n",
        "import networkx as nx\n",
        "import numpy as np\n",
        "from cirq.contrib.svg import SVGCircuit, circuit_to_svg\n",
        "\n",
        "from recirq.qaoa.classical_angle_optimization import OptimizationResult\n",
        "from recirq.qaoa.problems import get_all_hardware_grid_problems"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_BlXR0TaKtZO"
      },
      "source": [
        "Set the theme colors:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "gpkMGhaDIfBY"
      },
      "outputs": [],
      "source": [
        "QBLUE = '#1967d2'\n",
        "QRED = '#ea4335ff'\n",
        "QGOLD = '#fbbc05ff'"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vaaEu_xiLCav"
      },
      "source": [
        "## Create a grid"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LwpereqKIfBe"
      },
      "source": [
        "Here, we'll generate a 3x3 grid with arbitrarily chosen (fake!) beta, gamma parameters. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Von9l7KmIfBf"
      },
      "outputs": [],
      "source": [
        "fake_device_graph = nx.grid_2d_graph(3, 3)\n",
        "fake_device_graph = nx.relabel_nodes(\n",
        "    fake_device_graph, mapping={(r, c): cirq.GridQubit(r, c)\n",
        "                                for r, c in fake_device_graph.nodes})\n",
        "\n",
        "problems = get_all_hardware_grid_problems(fake_device_graph, central_qubit=cirq.GridQubit(1, 1),\n",
        "                                          n_instances=10, rs=np.random.RandomState(52))\n",
        "n_qubits = 9\n",
        "instance_i = 0\n",
        "problem = problems[n_qubits, instance_i]\n",
        "\n",
        "optimum = OptimizationResult(p=1, f_val=None, gammas=[0.123], betas=[0.456], min_c=None, max_c=None)\n",
        "nx.draw_networkx(problem.graph, \n",
        "                 pos={i: problem.coordinates[i] for i in range(problem.graph.number_of_nodes())},\n",
        "                 node_color=QBLUE)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xEgQ3mcrIfBj"
      },
      "source": [
        "If, however, you've been following along, we can load in the results of `HardwareGridProblemGenerationTask`s for which we've actually pre-computed the optimal angles. TODO: enable."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cQlwHhzLIfBk"
      },
      "source": [
        "```\n",
        "from recirq.qaoa.experiments.problem_generation_tasks import HardwareGridProblemGenerationTask\n",
        "from recirq.qaoa.experiments.angle_precomputation_tasks import AnglePrecomputationTask\n",
        "\n",
        "gen_task = HardwareGridProblemGenerationTask(\n",
        "    dataset_id = '2020-03-19',\n",
        "    device_name = 'Sycamore23',\n",
        "    instance_i = 0,\n",
        "    n_qubits = 5,\n",
        ")\n",
        "\n",
        "pre_task = AnglePrecomputationTask(\n",
        "    dataset_id = '2020-03-23',\n",
        "    generation_task = gen_task,\n",
        "    p = 1,\n",
        ")\n",
        "print(gen_task)\n",
        "print(pre_task)\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZuiLBEqgIfBl"
      },
      "source": [
        "```\n",
        "from recirq.qaoa.experiments.problem_generation_tasks import DEFAULT_BASE_DIR as PGEN_BASE_DIR\n",
        "from recirq.qaoa.experiments.angle_precomputation_tasks import DEFAULT_BASE_DIR as APRE_BASE_DIR\n",
        "\n",
        "gen_data = recirq.load(gen_task, base_dir=PGEN_BASE_DIR)\n",
        "pre_data = recirq.load(pre_task, base_dir=APRE_BASE_DIR)\n",
        "problem = gen_data['problem']\n",
        "optimum = pre_data['optimum']\n",
        "print(optimum)\n",
        "nx.draw_networkx(problem.graph, \n",
        "                 pos={i: problem.coordinates[i] for i in range(problem.graph.number_of_nodes())},\n",
        "                 node_color=QBLUE\n",
        "                )\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KuvSKzhdIfBm"
      },
      "source": [
        "## Ansatz\n",
        "\n",
        "As always, the circuit ansatz involves $|+\\rangle$ initialization followed by alternating applications of the problem and driver unitaries. We first construct a highly abstracted circuit with these multi-qubit operations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "9lQgwJfpIfBn"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import ProblemUnitary, DriverUnitary\n",
        "qubits = cirq.LineQubit.range(problem.graph.number_of_nodes())\n",
        "\n",
        "circuit = cirq.Circuit(\n",
        "    cirq.H.on_each(qubits),\n",
        "    ProblemUnitary(problem.graph, gamma=optimum.gammas[0]).on(*qubits),\n",
        "    DriverUnitary(len(qubits), beta=optimum.betas[0]).on(*qubits)\n",
        ")\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HrL9lTEaIfBr"
      },
      "source": [
        "## Harware topology\n",
        "\n",
        "We can enact the problem unitary with four entangling layers per p-step. \n",
        "\n",
        " 1. Horizontal links from even columns\n",
        " 2. Horizontal links from odd columns\n",
        " 3. Vertical links from even rows\n",
        " 4. Vertical links from odd rows\n",
        " \n",
        "To help the algorithm, we must specify `coordinates` to the compilation routine. This maps from bit indices $\\in \\{0, 1, \\dots n\\}$ to `(row, column)` coordinates so the compilation routine can categorize the various links into the above four categories. This is a little roundabout since we'll be mapping to `GridQubit`s, but I'm trying to emphasize the distinction between the problem (which is not related to quantum computing) and the implementation (which is).\n",
        " \n",
        "As always, the driver unitary is nothing more than single-qubit X rotations."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "98OkZWSiIfBs"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import compile_problem_unitary_to_hardware_graph, \\\n",
        "                                              compile_driver_unitary_to_rx\n",
        "circuit = compile_problem_unitary_to_hardware_graph(circuit, problem.coordinates)\n",
        "circuit = compile_driver_unitary_to_rx(circuit)\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0XCHWxQwIfBw"
      },
      "source": [
        "## Compilation\n",
        "\n",
        "To compile $e^{i \\gamma w_{ij} Z_i Z_j}$, express the `ZZ` interaction as three rounds of `SYC` gates. We take a brief aside to look at this compilation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "RDDbNl50IfBx"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "zz = cirq.Circuit(cirq.ZZ(*qubits[:2])**(2*0.345/np.pi))\n",
        "SVGCircuit(zz)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2QvEh_uFIfB0"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import compile_to_syc\n",
        "zz = compile_to_syc(zz)\n",
        "SVGCircuit(zz)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xkudCJcDIfB4"
      },
      "source": [
        "### Function `zz_as_syc` is included for convenience"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Fjl17Tq_IfB4"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import zz_as_syc\n",
        "zz = zz_as_syc(0.345, *qubits[:2])\n",
        "SVGCircuit(zz)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "4wYev76RIfB7"
      },
      "outputs": [],
      "source": [
        "cirq.testing.assert_allclose_up_to_global_phase(\n",
        "    cirq.Circuit(cirq.ZZ(*qubits[:2])**(2*0.345/np.pi)).unitary(),\n",
        "    zz_as_syc(0.345, *qubits[:2]).unitary(),\n",
        "    atol=1e-8\n",
        ")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "xvunS9GlIfB_"
      },
      "outputs": [],
      "source": [
        "cirq.testing.assert_allclose_up_to_global_phase(\n",
        "    compile_to_syc(cirq.Circuit(cirq.ZZ(*qubits[:2])**(2*0.345/np.pi))).unitary(),\n",
        "    zz_as_syc(0.345, *qubits[:2]).unitary(),\n",
        "    atol=1e-8\n",
        ")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rapp3N1IIfCB"
      },
      "source": [
        "### Structure the gates\n",
        "\n",
        "Make sure all the gates are well-structured. This means each layer is composed of homogeneous operations which are native to the device."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Ya-8Lq1EIfCC"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.circuit_structure import validate_well_structured\n",
        "_, stats = validate_well_structured(zz)\n",
        "stats"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fV0OaST0IfCG"
      },
      "source": [
        "## Compiling to native operations\n",
        "\n",
        "We use the above compilation of `ZZ` to compile our circuit to native operations. Because our compilation produces well-structured gates and our starting circuit was structured, the resulting circuit is well-structured."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "WmPRXvXbIfCH"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import compile_to_syc\n",
        "circuit = compile_to_syc(circuit)\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "e5S5y1qnIfCK"
      },
      "outputs": [],
      "source": [
        "_, stats = validate_well_structured(circuit)\n",
        "stats"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zVOUhlpOIfCN"
      },
      "source": [
        "## Append measurement"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "xrGIYwGSIfCO"
      },
      "outputs": [],
      "source": [
        "mcircuit = circuit + cirq.measure(*qubits, key='z')\n",
        "SVGCircuit(mcircuit)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "PTr54AsaIfCR"
      },
      "outputs": [],
      "source": [
        "_, stats = validate_well_structured(mcircuit)\n",
        "stats"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s7YGb2OVIfCU"
      },
      "source": [
        "## Compile out Z's\n",
        "Z gates commute through SYC so we can remove them. This step is not necessary: the quantum operating system will track the virtual Zs if we don't remove them."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "rMcZ3yOmIfCV"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import compile_out_virtual_z\n",
        "mcircuit = compile_out_virtual_z(mcircuit)\n",
        "SVGCircuit(mcircuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AdKNvgbhIfCZ"
      },
      "source": [
        "## Compile out negligible gates\n",
        "\n",
        "We've left several `PhX^0` to keep our circuits structured. As the very last compilation step, we can drop these."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ejJTtjj9IfCZ"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.gates_and_compilation import compile_to_non_negligible\n",
        "mcircuit = compile_to_non_negligible(mcircuit)\n",
        "SVGCircuit(mcircuit)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "bFz9dhyfIfCc"
      },
      "outputs": [],
      "source": [
        "_, stats = validate_well_structured(mcircuit)\n",
        "stats"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PRR0w98_IfCf"
      },
      "source": [
        "## Place on device\n",
        "\n",
        " - Our problem has integer nodes because it should be specified independently of a quantum implementation\n",
        " - Our circuit has LineQubit qubits to emphasize the fact that we can place this circuit in multiple locations on a device\n",
        " - Our `coordinates` list was used only as a helper for the compilation\n",
        " \n",
        "We now place the compiled circuit onto a compatible part of the device. Here, we use networkx's subgraph isomorphism routine to find all the possibilities."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5p5qjKgAIfCg"
      },
      "outputs": [],
      "source": [
        "from cirq.contrib.routing import xmon_device_to_graph\n",
        "device_graph = xmon_device_to_graph(recirq.get_device_obj_by_name('Sycamore23'))\n",
        "nx.draw_networkx(device_graph, pos={q: (q.row, q.col) for q in device_graph.nodes}, node_color=QRED)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "pxRXrpCvIfCp"
      },
      "outputs": [],
      "source": [
        "from matplotlib import pyplot as plt\n",
        "from cirq.contrib.routing import xmon_device_to_graph\n",
        "device_graph = xmon_device_to_graph(recirq.get_device_obj_by_name('Sycamore23'))\n",
        "matcher = nx.algorithms.isomorphism.GraphMatcher(device_graph, problem.graph)\n",
        "\n",
        "# There's a \"rotational\" freedom which we remove here:\n",
        "each_set_of_qubits_only_one_subgraph = {}\n",
        "for q_to_i in matcher.subgraph_isomorphisms_iter():\n",
        "    each_set_of_qubits_only_one_subgraph[frozenset(q_to_i.keys())] = q_to_i\n",
        "\n",
        "for q_to_i in each_set_of_qubits_only_one_subgraph.values():\n",
        "    nx.draw_networkx(device_graph, pos={q: (q.row, q.col) for q in device_graph.nodes},\n",
        "                     node_color=[QRED if q in q_to_i else QBLUE for q in device_graph.nodes])\n",
        "    plt.show()\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "arUdjiqHIfCs"
      },
      "outputs": [],
      "source": [
        "i_to_q = {i: q for q, i in q_to_i.items()}\n",
        "# Since our nodes are contiguous integers starting from 0, we can flatten into a list\n",
        "device_qubits = [i_to_q[i] for i in range(len(i_to_q))]\n",
        "del i_to_q\n",
        "\n",
        "def _mapq(q):\n",
        "    return device_qubits[q.x]\n",
        "\n",
        "mcircuit = mcircuit.transform_qubits(_mapq)\n",
        "SVGCircuit(mcircuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "swSxqi6jIfCu"
      },
      "source": [
        "## Problem circuit functions"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "SgGS1rpjIfCv"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problem_circuits import get_generic_qaoa_circuit\n",
        "circuit = get_generic_qaoa_circuit(\n",
        "    problem_graph=problem.graph, \n",
        "    qubits=qubits, \n",
        "    gammas=[0.123], \n",
        "    betas=[0.456],\n",
        ")\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "pBd8nsknIfCx"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problem_circuits import get_routed_hardware_grid_circuit\n",
        "circuit = get_routed_hardware_grid_circuit(\n",
        "    problem_graph=problem.graph,\n",
        "    qubits=qubits,\n",
        "    coordinates=problem.coordinates,\n",
        "    gammas=[0.123],\n",
        "    betas=[0.456],\n",
        ")\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "loLXlfMEIfC0"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problem_circuits import get_compiled_hardware_grid_circuit\n",
        "circuit, qubits = get_compiled_hardware_grid_circuit(\n",
        "    problem=problem,\n",
        "    qubits=device_qubits,\n",
        "    gammas=[0.123],\n",
        "    betas=[0.456],\n",
        ")\n",
        "SVGCircuit(circuit)"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "hardware_grid_circuits.ipynb",
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
